﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TextJustification
{
    public class Test
    {
        static int[,] cost = null;
        static string[] words = null;
        static int width = 120;
        public static void Main(string[] args)
        {
            width = 120;
            //string input = "tushar rai likes to code";
            string input = File.ReadAllText("test.txt");
            words = input.Split(' ');
            cost = new int[words.Length, words.Length];
            int[] result = new int[words.Length + 1];
            int[] pos = new int[words.Length + 1];
            BuildCostMatrix();
            pos[words.Length - 1] = words.Length - 1;
            result[words.Length - 1] = 0;  //cost[words.Length - 1, words.Length - 1];
            
            for (int i = result.Length - 2; i >= 0; i--)
            {
                int min = 1000000, newMin = 0, breaker = 0, k = 0;
                for (int j = i + 1; j < result.Length ; j++)
                {
                    newMin = result[j] + cost[i, j - 1];
                    if (newMin < min)
                    {
                        min = newMin;
                        breaker = j - 1;
                    }
                }
                result[i] = min;
                pos[i] = breaker;
            }
            Console.WriteLine("Result: " + result[0]);
            for (int i = 0; i < pos.Length - 1; i++)
            {
                for (int j = i; j <= pos[i]; j++)
                    Console.Write(words[j] + " ");
                Console.WriteLine();
                i = pos[i];
            }
            Console.ReadLine();
        }

        public static void BuildCostMatrix()
        {
            
            for (int i = 0; i < words.Length; i++)
            {
                int totalLength = 0;
                for (int j = i; j < words.Length; j++)
                {
                    totalLength += words[j].Length;
                    if (width >= totalLength)
                        cost[i, j] = (width - totalLength) * (width - totalLength);
                    else
                    {
                        cost[i, j] = 1000000;
                    }
                    totalLength++;
                }
            }
        }
    }
}
